package link_list



func getIntersectionNode(headA, headB *ListNode) *ListNode {
	if headA == nil || headB == nil {
		return nil
	}
	p1, p2 := headA, headB  // 初始两个指针分别指向两个链表的头部
	n := 0                  // 初始化n记录步长
	for p1.Next != nil {
		p1 = p1.Next        // 第一个链表开始走，直到走到最后一个节点
		n++                 // 记录走过的步数
	}
	for p2.Next != nil {
		p2 = p2.Next        // 第二个链表开始走，直到走到最后一个节点
		n--                 // 每走一步第一个指针走过的步数减一，最后得到步数差
	}
	if p1 != p2 {           // p1 p2 不相等则不相交，直接返回nil
		return nil
	}
	p1, p2 = headA, headB   // 回到开头
	if n < 0 {              // 如果n小于0，则p1走的步数小于p2
		p1, p2 = p2, p1     // 调换p1 与 p2，使p1始终指向长一点的链表
	}
	n = abs(n)
	for n != 0 { 			// 长的链表先走步差
		p1 = p1.Next
		n--
	}
	for p1 != p2 {          // 同时走找到第一个相遇的节点，即为第一个相交的节点
		p1 = p1.Next
		p2 = p2.Next
	}
	return p1
}

func abs(n int) int {
	if n < 0 {
		return -n
	}
	return n
}
